package org.example.Greedy_Algorithm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

public class Partition_letter {
    public static void main(String[] args) {
        //划分字母区间

        //给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
        //注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
        //返回一个表示每个字符串片段的长度的列表。
        String s = "ababcbacadefegdehijhklij";
        List<Integer> list = partitionLabels(s);
        System.out.println(list.toString());
    }
    public static List<Integer> partitionLabels(String s) {
        ArrayList<Integer> list = new ArrayList<>();
        StringBuilder sb = new StringBuilder(s);
        HashMap<Character, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < sb.length(); i++) {
            hashMap.put(sb.charAt(i),i);
        }
        for (int i = 0; i < sb.length(); i++) {
            char c = sb.charAt(i);
            Integer index = hashMap.get(c);
            for (int j = i+1; j < index; j++) {
                char inner = sb.charAt(j);
                if (hashMap.get(inner)>index){
                    index = hashMap.get(inner);
                }
            }
            list.add(index-i+1);
            i = index;
        }
        return list;
    }
}
